package ai;

import util.List;

public class Sort {

	public final static void quickSort(List v, int head, int tail) {
		if (head < tail) {
			int pivotIndex = (head + tail) / 2;
			Comparable pivot = (Comparable) v.get(pivotIndex);
			int i = head - 1;
			int j = tail + 1;
			do {
				do i++;
				while (pivot.compareTo((v.get(i)))<0);
				do j--;
				while (((Comparable) v.get(j)).compareTo(pivot)<0);
				if (i < j)
					swap(v, i, j);
			}
			while (i < j);
			if (i == j) {
				quickSort(v, head, j - 1);
				quickSort(v, i + 1, tail);
			} else {
				quickSort(v, head, j);
				quickSort(v, i, tail);
			}
		}
	}

	public final static void swap(List v, int i, int j) {
		Object obj = v.get(i);
		v.set(i, v.get(j));
		v.set(j, obj);
	}

}
